package me.qingy.old.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author qingy
 * @since 2021/1/17
 */
public class ThreeSum {
    /**
     * X =>️ 暴力穷举法 与 Map登记法都有时间复杂度高、逻辑复杂的问题
     * 双指针法（分治）
     * 时间复杂度 O(n^2) 空间复杂度 O(1)
     */
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);

        // 循环中声明lp与rp为i的衍生指针，即以i为核心
        for (int i = 0; i < n; i++) {
            // 如果数值大于0，没有继续的必要，退出循环
            if (nums[i] > 0) break;
            // i指针去重 为什么不能用nums[i+1]去重？因为那样会少一圈左指针遍历
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int lp = i + 1;
            int rp = n - 1;

            // 双指针移动
            while (lp < rp) {
                int sum = nums[i] + nums[lp] + nums[rp];
                // 如果sum等于0 双指针同时移动并去重 因为同样的组合只能出现一种
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[lp], nums[rp]));

                    lp++;
                    rp--;

                    // lp指针去重 依然需要lp指针在rp指针左边条件，别移过头
                    while (lp < rp && nums[lp] == nums[lp - 1]) lp++;
                    // rp指针去重
                    while (lp < rp && nums[rp] == nums[rp + 1]) rp--;
                }
                else if (sum < 0)
                    lp++;
                else
                    rp--;
            }

        }
        return result;
    }
}
